package com.leetcode.algorithm.y21.m07;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * leetcode-cn.com
 * 滑动窗口
 * 
 * @author jie.deng
 *
 */
public class MySolution0728 {
	
    /**
     * 3. 无重复字符的最长子串
     * 
     * 
	 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
	 * 
	 *  
	 * 
	 * 示例 1:
	 * 
	 * 输入: s = "abcabcbb"
	 * 输出: 3 
	 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
	 * 示例 2:
	 * 
	 * 输入: s = "bbbbb"
	 * 输出: 1
	 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
	 * 示例 3:
	 * 
	 * 输入: s = "pwwkew"
	 * 输出: 3
	 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
	 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
	 * 示例 4:
	 * 
	 * 输入: s = ""
	 * 输出: 0
	 *  
	 * 
	 * 提示：
	 * 
	 * 0 <= s.length <= 5 * 104
	 * s 由英文字母、数字、符号和空格组成
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @return
     */
	public int lengthOfLongestSubstring(String s) {
		// Step 1: 定义需要维护的变量
		// maxLen ：最长子串的长度
		int maxLen = 0;
		// cntMap<K,V> ：在字符串s中字符K出现的最大索引
		Map<Character, Integer> maxIdxMap = new HashMap<>();
		
		// Step 2: 定义窗口的首尾端 (left, right)， 然后滑动窗口
		int left = 0;
		for (int right = 0; right < s.length(); right++) {
			// Step 3: 需要改变左索引的情况：改变左索引前，更新需要维护的变量
			Character ch = Character.valueOf(s.charAt(right));
			if (maxIdxMap.containsKey(ch)) {
				left = Math.max(left, maxIdxMap.get(ch).intValue() + 1);
			}
			
			// 更新需要维护的变量
			maxIdxMap.put(ch, right);
			maxLen = Math.max(maxLen, right - left + 1);
			// Step 4: 改变右索引
		}
		
		// Step 5: 返回答案
		return maxLen;
	}
	
    /**
     * 209. 长度最小的子数组
     * 
     * 给定一个含有 n 个正整数的数组和一个正整数 target 。
     * 
     * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
     * 
     *  
     * 
     * 示例 1：
     * 
     * 输入：target = 7, nums = [2,3,1,2,4,3]
     * 输出：2
     * 解释：子数组 [4,3] 是该条件下的长度最小的子数组。
     * 示例 2：
     * 
     * 输入：target = 4, nums = [1,4,4]
     * 输出：1
     * 示例 3：
     * 
     * 输入：target = 11, nums = [1,1,1,1,1,1,1,1]
     * 输出：0
     *  
     * 
     * 提示：
     * 
     * 1 <= target <= 109
     * 1 <= nums.length <= 105
     * 1 <= nums[i] <= 105
     *  
     * 
     * 进阶：
     * 
     * 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
     * 
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param target
     * @param nums
     * @return
     */
	public int minSubArrayLen(int target, int[] nums) {
		// Step 1: 定义需要维护的变量
		int minLen = Integer.MAX_VALUE;
		int sum = 0;
		
		// 窗口: 满足其和 ≥ target 的连续子数组。
		// 移动窗口的起始位置: 子数组之和 ≥ target
		// 移动窗口的结束位置: 子数组之和 < target
		// Step 2: 定义窗口的首尾端 (left, right)， 然后滑动窗口
		int left = 0;
		for (int right = 0; right < nums.length; right++) {
			// Step 3: 滑动窗口右索引改变前，更新需要维护的变量
			sum += nums[right];
			if (sum >= target) {
				minLen = Math.min(right - left + 1, minLen);
			}

			// Step 4: 改变左索引
			while (sum >= target && left < right) {
				// 滑动窗口左索引改变前，更新需要维护的变量
				sum -= nums[left++];
				if (sum >= target) {
					minLen = Math.min(right - left + 1, minLen);
				}
			}
		}

		// Step 5: 返回答案
		return minLen == Integer.MAX_VALUE ? 0 : minLen;
	}
	
    /**
     * 438. 找到字符串中所有字母异位词
     * 
	 * 给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
	 * 
	 * 异位词 指字母相同，但排列不同的字符串。
	 * 
	 *  
	 * 
	 * 示例 1:
	 * 
	 * 输入: s = "cbaebabacd", p = "abc"
	 * 输出: [0,6]
	 * 解释:
	 * 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
	 * 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
	 *  示例 2:
	 * 
	 * 输入: s = "abab", p = "ab"
	 * 输出: [0,1,2]
	 * 解释:
	 * 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
	 * 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
	 * 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
	 *  
	 * 
	 * 提示:
	 * 
	 * 1 <= s.length, p.length <= 3 * 104
	 * s 和 p 仅包含小写字母
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/find-all-anagrams-in-a-string
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param s
     * @param p
     * @return
     */
	public List<Integer> findAnagrams(String s, String p) {
		List<Integer> retList = new ArrayList<>();
		int winSize = p.length();
		if (s.length() < winSize) {
			return retList;
		}
		// cntArr[i]表示子串包含字符('a'+i)的个数
		int[] targetCntArr = new int[26];
		for (int i = 0; i < winSize; i++) {
			targetCntArr[p.charAt(i) - 'a'] += 1;
		}
		int[] cntArr = new int[26];

		int idx = 0;
		for (; idx < winSize; idx++) {
			cntArr[s.charAt(idx) - 'a'] += 1;
		}
		if (Arrays.equals(targetCntArr, cntArr)) {
			retList.add(Integer.valueOf(idx - winSize));
		}

		for (; idx < s.length(); idx++) {
			cntArr[s.charAt(idx - winSize) - 'a'] -= 1;
			cntArr[s.charAt(idx) - 'a'] += 1;
			if (Arrays.equals(targetCntArr, cntArr)) {
				retList.add(Integer.valueOf(idx - winSize + 1));
			}
		}

		return retList;
	}

	/**
	 * 567. 字符串的排列
	 * 
	 * 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。
	 * 
	 * 换句话说，第一个字符串的排列之一是第二个字符串的 子串 。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入: s1 = "ab" s2 = "eidbaooo"
	 * 输出: True
	 * 解释: s2 包含 s1 的排列之一 ("ba").
	 * 示例 2：
	 * 
	 * 输入: s1= "ab" s2 = "eidboaoo"
	 * 输出: False
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= s1.length, s2.length <= 104
	 * s1 和 s2 仅包含小写字母
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/permutation-in-string
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
	 * 
	 * @param s1
	 * @param s2
	 * @return
	 */
	public boolean checkInclusion(String s1, String s2) {
		int winSize = s1.length();
		if (s2.length() < winSize) {
			return false;
		}
		// cntArr[i]表示子串包含字符('a'+i)的个数
		int[] targetCntArr = new int[26];
		for (int i = 0; i < winSize; i++) {
			targetCntArr[s1.charAt(i) - 'a'] += 1;
		}
		int[] cntArr = new int[26];

		int idx = 0;
		for (; idx < winSize; idx++) {
			cntArr[s2.charAt(idx) - 'a'] += 1;
		}
		if (Arrays.equals(targetCntArr, cntArr)) {
			return true;
		}

		for (; idx < s2.length(); idx++) {
			cntArr[s2.charAt(idx - winSize) - 'a'] -= 1;
			cntArr[s2.charAt(idx) - 'a'] += 1;
			if (Arrays.equals(targetCntArr, cntArr)) {
				return true;
			}
		}

		return false;
	}
	
    
    /**
     * 1004. 最大连续1的个数 III
     * 
	 * 给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。
	 * 
	 * 返回仅包含 1 的最长（连续）子数组的长度。
	 * 
	 *  
	 * 
	 * 示例 1：
	 * 
	 * 输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
	 * 输出：6
	 * 解释： 
	 * [1,1,1,0,0,1,1,1,1,1,1]
	 * 粗体数字从 0 翻转到 1，最长的子数组长度为 6。
	 * 示例 2：
	 * 
	 * 输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
	 * 输出：10
	 * 解释：
	 * [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
	 * 粗体数字从 0 翻转到 1，最长的子数组长度为 10。
	 *  
	 * 
	 * 提示：
	 * 
	 * 1 <= A.length <= 20000
	 * 0 <= K <= A.length
	 * A[i] 为 0 或 1 
	 * 
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/max-consecutive-ones-iii
	 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     * 
     * @param nums
     * @param k
     * @return
     */
	public int longestOnes(int[] nums, int k) {
		if (k >= nums.length) {
			return nums.length;
		}
		// Step 1: 定义需要维护的变量
		// maxLen表示最大连续1的个数
		int maxLen = 0;
		// cnt0表示0的个数
		int cnt0 = 0;

		// Step 2: 定义窗口的首尾端 (left, right)， 然后滑动窗口
		int left = 0;
		for (int right = 0; right < nums.length; right++) {
			// Step 3: 滑动窗口右索引改变前，更新需要维护的变量
			if (nums[right] == 0) {
				cnt0++;
				if (cnt0 <= k) {
					maxLen = Math.max(maxLen, right - left + 1);
				}
			} else {
				maxLen = Math.max(maxLen, right - left + 1);
			}

			// Step 4: 改变左索引
			while (cnt0 > k && left < right) {
				// 滑动窗口左索引改变前，更新需要维护的变量
				if (nums[left] == 0) {
					cnt0--;
				}
				left++;
			}
		}

		// Step 5: 返回答案
		return maxLen;
	}
}
